package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import lombok.AccessLevel;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <h1>有向图环检测<h1/>
 * <p>
 *     检测一个有向图，是否有环。
 * </p>
 * <p>
 *     核心思想：<br>
 *         dfs的实现方式有两种，一种是通过递归的方式；一种是通过stack for循环的方式。
 *         对于有向环检测，一般是使用递归的方式。
 * </p>
 */
public class DfsCycleCheck<T> {
    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private Graph<T> graph;

    private Set<Vertex<T>> onstack = new HashSet<>();


    private Set<Vertex<T>> visited = new HashSet<>();

    @Getter
    private boolean hasCycle = false;
    @Getter
    private Vertex<T> cycleVertex;


    private DfsCycleCheck cycleCheck(){
        graph.getVertices().entrySet().stream().map(Map.Entry::getValue).forEach(this::dfs);

        return this;
    }
    //遍历顶点
    private void dfs(Vertex<T> vertex){
        //退出条件

        if (hasCycle||visited.contains(vertex)) {
            return;
        }
        onstack.add(vertex);//记录在栈中
        visited.add(vertex);
        if(vertex.getNext()!=null){
            for(Edge<T> edge:vertex.getNext()){
                if(onstack.contains(edge.getTo())){
                    this.hasCycle = true;
                    this.cycleVertex = edge.getTo();
                    return;
                }
                dfs(edge.getTo());
            }
        }
        onstack.remove(vertex);//删除在栈记录

    }


    public static final <TT> DfsCycleCheck<TT> create(Graph<TT> graph){
        return new DfsCycleCheck<TT>().setGraph(graph).cycleCheck();
    }















}
